package com.leetcode.algorithm.y22.m06;

/**
 * 35. 搜索插入位置
 * 
 * https://leetcode.cn/problems/search-insert-position/
 * 
 * @author jie.deng
 *
 */
class Question0035Solution01 {
	
	public int searchInsert(int[] nums, int target) {
		// 前置条件：无重复元素
		// 找第一个大于等于给定值的元素的索引
		int left = 0;
		int right = nums.length - 1;
		int ret = nums.length;
		while (left <= right) {
			int mid = left + ((right - left) >> 1);
			if (nums[mid] == target) {
				return mid;
			} else if (nums[mid] < target) {
				left = mid + 1;
			} else {
				ret = mid;
				right = mid - 1;
			}
		}
		return ret;
	}
    
}